import { LinkedList, Node } from "./链表";

// 双向节点类
export class DoublyNode<T> extends Node<T> {
  next: DoublyNode<T> | null;
  prev: DoublyNode<T> | null;
  constructor(val: T) {
    super(val);
    this.prev = null;
    this.next = null;
  }
}

// 双向链表类
export class DoublyLinkedList<T = number> extends LinkedList<T> {
  protected head: DoublyNode<T> | null;
  protected tail: DoublyNode<T> | null;
  constructor() {
    super();
    this.tail = null;
    this.head = null;
  }
  // 根据索引插入函数，含重载
  findNodeByIndex(index: number): DoublyNode<T> | null;
  findNodeByIndex(index: number) {
    return super.findNodeByIndex(index);
  }
  // 插入尾部函数
  insertToTail(val: T): void {
    const node = new DoublyNode(val);
    if (this.head === null) {
      // 如果插入的时候是头节点
      this.head = node;
      this.tail = node;
    } else {
      if (this.tail == null) throw console.trace('意料之外的情况：，this.tail为null，参数：', val);
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    }
    this.length++;
  }
  // 根据索引插入函数
  insertByIndex(index: number, val: T): boolean {
    if (index < 0 || index > this.length) {
      console.warn("请检查输入的索引是否合理");
      return false;
    } else {
      const node = new DoublyNode(val);
      if (index === 0) {
        // 在链表的头部增加元素
        if (this.head === null) {
          // 链表的头部为空
          this.head = node;
          this.tail = node;
        } else {
          // 头部不为空
          node.next = this.head;
          this.head.prev = node;
          this.head = node;
        }
      } else if (index === this.length && this.tail) {
        // 在链表的末尾插入元素
        this.tail.next = node;
        node.prev = this.tail;
        this.tail = node;
      } else {
        // 在列表的中间插入元素
        const previous = this.findNodeByIndex(index - 1);
        if (previous == null || previous.next == null) {
          throw console.trace(`意料之外的情况：未搜索到插入前驱节点或插入节点的后继节点不存在，
          参数：${index},${val}`);
        }
        node.next = previous.next;
        node.prev = previous;
        previous.next.prev = node;
        previous.next = node;
      }
      this.length++;
      return true;
    }
  }
  // 移除链表任意位置元素
  deleteByIndex(index: number): null | DoublyNode<T> {
    if (!this.checkIndex(index)) {
      console.warn("请检查输入的索引是否合理");
      return null;
    } else {
      let curr = this.head;
      // 边缘情况，仅有一个元素时
      if (this.length === 1) {
        this.head = null;
        this.tail = null;
      } else if (index === 0 && curr && curr.next) {
        // 如果删除的位置位于头部        
        this.head = curr.next;
        this.head.prev = null;
      } else if (index === this.length - 1) {
        // 如果删除的位置位于尾部
        curr = this.tail;
        if (curr == null || curr.prev == null) {
          throw console.trace(`尾节点为空或者当前尾节点前驱位置为空，输入参数：
          ${index}`);
        }
        this.tail = curr.prev;
        this.tail.next = null;
      } else {
        // 如果删除的位置位于中间位置
        curr = this.findNodeByIndex(index);
        if (curr == null || curr.next == null || curr.prev == null) {
          throw console.trace(`意料之外的情况：删除链表落于中间位置而链表长度小于3，输入参数：
          ${index}`);
        }
        const prev = curr.prev;
        prev.next = curr.next;
        prev.next.prev = prev;
      }
      this.length--;
      return curr;
    }
  }
  // 获取链表尾部的元素
  getTail(): DoublyNode<T> | null {
    return this.tail;
  }
  // 清空链表
  clear(): void {
    this.tail = null;
    this.head = null;
    this.length = 0;
  }
  // 串行字符串化链表
  stringfy(): string {
    let tailStr = "";
    let curr = this.tail;
    for (let i = this.length - 1; i >= 0 && curr; i--) {
      tailStr = "<---" + curr!.val + tailStr;
      curr = curr.prev;
    }
    return `
    ${super.stringfy()}
    ${tailStr.slice(4, tailStr.length)}
    `;
  }
}


// 测试用例
const doublyLinkedList = new DoublyLinkedList();
// 双向链表尾部插入元素
doublyLinkedList.insertToTail(12);
doublyLinkedList.deleteByIndex(0);
doublyLinkedList.insertToTail(14);
doublyLinkedList.insertToTail(16);
// 删除头节点
doublyLinkedList.deleteByIndex(0);
// 删除尾节点
doublyLinkedList.deleteByIndex(1);
// 双向链表任意位置插入元素
doublyLinkedList.insertByIndex(0, 13);
doublyLinkedList.insertByIndex(1, 11);
doublyLinkedList.insertByIndex(2, 14);
//移除指定位置元素
doublyLinkedList.deleteByIndex(3);
doublyLinkedList.insertByIndex(4, 15);
console.log(doublyLinkedList.stringfy());
// 获取链表尾部元素
console.log(doublyLinkedList.getTail());

// 获取链表长度
console.log("链表长度", doublyLinkedList.getLength())
doublyLinkedList.deleteByIndex(2);

// 清空链表
doublyLinkedList.clear();
console.log(doublyLinkedList.stringfy());
console.log(doublyLinkedList.isEmpty());
